// @algorithm @lc id=100313 lang=cpp
// @title shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof

#include "algm/algm.h"
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    int findNthDigit(int n) {
        if (n == 0) {
            return n;
        }
        // 找到第n位的数字的位数width
        int width = 1;
        while (n > (width * 9 * pow(10, width - 1))) {
            n -= (width * 9 * pow(10, width - 1));
            ++width;
        }
        // index为在该数位等级的第几个数字
        // pos为在该数字的第几位
        int index = n / width;
        int pos = n % width;
        int ans = -1;
        int targetNum = pow(10, width - 1) + index;
        if (pos == 0) {
            targetNum -= 1;
            pos = width;
        }
        cout << "targetNum = " << targetNum << endl;
        cout << "pos = " << pos << endl;
        while (width != pos - 1) {
            ans = targetNum % 10;
            targetNum /= 10;
            --width;
        }
        return ans;
    }
};